#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
从中间向两边扩散
"""

class Solution:
    def __init__(self, digit):
        self.digit = digit          # 二进制位个数

        self.len = (2**self.digit)
        self.results =  self.len * [0]

    def calc(self):
        # ------------------- depth 0 ---------------------
        base0 = self.digit * [0]
        base1 = self.digit * [0]
        # base1[0] = 1
        base1[-1] = 1

        base0_idx = self.len // 2 - 1
        base1_idx = base0_idx + 1

        self.results[base0_idx] = base0
        self.results[base1_idx] = base1

        # ------------------- depth proceed ---------------------
        self.expand_rec(1, base0_idx, base1_idx)

    def expand_rec(self, n, base0_idx, base1_idx):
        if n == self.digit:
            return

        copy_num = 2**(n-1)     # 每次翻倍

        # ------------------- up/left ---------------------
        for dis in range(copy_num):
            self.results[base0_idx - dis - 1] = self.copy(self.results[base0_idx+dis], n)

        base0_idx = base0_idx - dis - 1

        # ------------------- down/right ---------------------
        for dis in range(copy_num):
            self.results[base1_idx + dis + 1] = self.copy(self.results[base1_idx-dis], n)

        base1_idx = base1_idx + dis + 1

        self.expand_rec(n+1, base0_idx, base1_idx)

    def copy(self, ele, n):
        c = list(ele)

        # assert c[n] == 0
        # c[n] = 1

        idx = -n - 1
        assert c[-n-1] == 0
        c[-n-1] = 1

        return c

def check_only_1_diff(a, b):
    cnt = 0
    for i in range(len(a)):
        if a[i] != b[i]: cnt += 1

    return cnt == 1

def valid(lst):
    for i in range(len(lst)-1):
        if not check_only_1_diff(lst[i], lst[i+1]):
            return False
    return check_only_1_diff(lst[0], lst[-1])

def test():
    s = Solution(15)
    s.calc()
    # print(s.results)
    valid(s.results)

    not valid([ [0, 0, 1], [1, 1, 1]])

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
